﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DK.StackCalculator.Demo;
public class StackCalculatorPostfixExpression
{
    /*
     * 1.开始扫描
     * 
     * 2.扫到数字,直接加入后缀表达式
     * 
     * 3.扫到运算符时:
     * 4.扫到"("入栈,遇到")"时则把栈中运算符加入后缀表达式中,直到出现"(",并让其出栈。
     * 5.扫到运算符高于栈顶运算符时入栈,低于栈顶运算符时从栈顶出栈运算符到后缀表达式,
     *   直到出一个比它优先级低的运算符或"("。
     *   （扫符比栈，栈低则入，栈高或左阔则出）
     *   
     * 6.当扫描的中缀表达式结束时，栈中的的所有运算符出栈
     */

    /// <summary>
    /// 处理括号运算符
    /// </summary>
    /// <param name="oper"></param>
    /// <param name="stack"></param>
    /// <param name="ipexpression"></param>
    private void OtherOperatorHandle(char oper, Stack<char> stack, ref string ipexpression)
    {
        if (oper.Equals('('))
        {
            stack.Push(oper);
        }
        else if (oper.Equals(')'))
        {
            while (!stack.Peek().Equals('('))
            {
                ipexpression += stack.Pop();
            }
            if (stack.Peek().Equals('(')) stack.Pop();
        }
    }

    /// <summary>
    /// 处理非括号运算符（加减乘除）
    /// </summary>
    /// <param name="oper"></param>
    /// <param name="stack"></param>
    /// <param name="ipexpression"></param>
    private void MainOperatorHandle(char oper, Stack<char> stack, ref string ipexpression)
    {
        while (stack.Count > 0 && GetPriority(oper) < GetPriority(stack.Peek()))
        {
            ipexpression += stack.Pop();
        }
        stack.Push(oper);
    }

    /// <summary>
    /// 中缀表达式转逆波兰表达式
    /// </summary>
    /// <param name="expression"></param>
    /// <returns></returns>
    public string GetInversePolishExpression(string expression)
    {
        expression = expression.Replace(" ", "");
        string ipexp = "";
        var charStack = new Stack<char>();
        for (int i = 0; i < expression.Length; i++)
        {
            if (IsOper(expression[i]))
            {
                if (GetPriority(expression[i]).Equals(int.MinValue))
                {
                    OtherOperatorHandle(expression[i], charStack, ref ipexp);
                }
                else
                {
                    MainOperatorHandle(expression[i], charStack, ref ipexp);
                }
            }
            else
            {
                ipexp += expression[i];
            }
        }
        foreach (var item in charStack)
        {
            ipexp += item;
        }
        return ipexp;
    }

    /// <summary>
    /// 逆表达式计算
    /// </summary>
    /// <param name="ipExpression">逆波兰表达式</param>
    /// <returns></returns>
    /// <exception cref="DataMisalignedException"></exception>
    public int Compute(string ipExpression) 
    {
        var numberStack = new Stack<int>(); 
        foreach (var item in ipExpression)
        {
            if (IsOper(item))
            {
                numberStack.Push(Operation(numberStack.Pop(),numberStack.Pop(),item));
            }
            else if (IsNumber(item))
            {
                numberStack.Push(item);
            }
            else 
            {
                throw new DataMisalignedException("data type error.");
            }
        }

        return numberStack.Pop();
    }

    /// <summary>
    /// 判断是否为运算符
    /// </summary>
    /// <param name="oper"></param>
    /// <returns></returns>
    private bool IsOper(char oper)
    {
        return oper == '+' || oper == '-' || oper == '*' || oper == '/' || oper == '(' || oper == ')';
    }

    /// <summary>
    /// 判断是否为数字
    /// </summary>
    /// <param name="oper"></param>
    /// <returns></returns>
    private bool IsNumber(char oper)
    {
        return oper >= 48 && oper <= 57;
    }

    /// <summary>
    /// 判断优先级
    /// </summary>
    /// <param name="oper"></param>
    /// <returns></returns>
    /// <exception cref="Exception"></exception>
    private int GetPriority(char oper)
    {
        if (oper == '(' || oper == ')') return int.MinValue;
        else if (oper == '*' || oper == '/') return 1;
        else if (oper == '+' || oper == '-') return 0;
        else throw new Exception("invalid character.");
    }

    /// <summary>
    /// 运算
    /// </summary>
    /// <param name="n1"></param>
    /// <param name="n2"></param>
    /// <param name="oper"></param>
    /// <returns></returns>
    /// <exception cref="Exception"></exception>
    private int Operation(int n1, int n2, char oper)
    {
        int value;
        switch (oper)
        {
            case '+':
                value = n2 + n1;
                break;
            case '-':
                value = n2 - n1;
                break;
            case '*':
                value = n2 * n1;
                break;
            case '/':
                value = n2 / n1;
                break;
            default:
                throw new Exception("invalid character.");
        }
        return value;
    }


}
